﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 两数之和
{
    class Program
    {
        public int[] TwoSum(int[] nums, int target)
        {
            int[] result = new int[2];
            Dictionary<int, int> dict = new Dictionary<int, int>();

            for (int i = 0; i < nums.Length; i++)
            {
                int complement = target - nums[i];
                if (dict.ContainsValue(complement))
                {
                    int a =0;
                    foreach (var item in dict)
                    {
                        if(item.Value == complement)
                        {
                            a = item.Key;
                            break;
                        }
                    }
                    result[0] = a;
                    result[1] = i;
                    return result;
                }
                else
                {

                    dict.Add(i, nums[i]);
                }
            }
            return null;
        }
        public int[] TwoSum1(int[] nums, int target)
        {
            int[] result = new int[2];
            Dictionary<int, int> dict = new Dictionary<int, int>();

            for (int i = 0; i < nums.Length; i++)
            {
                int complement = target - nums[i];
                if (dict.ContainsKey(complement))
                {
                    result[0] = dict[complement];
                    result[1] = i;
                    return result;
                }
                else
                {
                    //错误写法，key有可能重复
                    //dict.Add(nums[i], i);
                    //直接可以更新value值，因为一旦替换逻辑成立说明重复的值不可能称为答案，可以自己用例子验证
                    dict[nums[i]] = i;
                }
            }

            return null;
        }
        public int[] TwoSum2(int[] nums, int target)
        {
            int[] Two = new int[2];
            for (int i = 0; i < nums.Length - 1; i++)
            {
                for (int j = i + 1; j < nums.Length; j++)
                {
                    if (nums[i] + nums[j] == target)
                    {
                        Two[0] = i;
                        Two[1] = j;
                        return Two;
                    }

                }
            }
            return null;
        }
    }
}
